import java.util.Arrays;

/**
 * 870.优势洗牌
 */
public class Exerciser2 {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        // 先把 nums1 进行排序，排成升序
        // 再使用 index 下标数组，根据 nums2 的值的大小排成升序对应的下标
        // 使用排好的nums1 从0~n-1 和 index中的 0~n-1 中的数据对应的 nums2 中的数据进行和nums1 比较
        // 最佳策略：
        // 1.如果比不过，就去拖累nums2中额的最大值
        // 2.如果能比过，那就直接比
        int n = nums1.length;
        // 对nums1排序
        Arrays.sort(nums1);
        // 创建 index 数组，根据 nums2 的值进行排序
        Integer[] index = new Integer[n];
        // 对其进行根据 nums2 进行排序
        for(int i = 0;i < n;i++) {
            index[i] = i;
        }
        Arrays.sort(index,(i,j) -> {
            return nums2[i] - nums2[j];
        });

        // 进行比较
        int[] ret = new int[n];
        int left = 0;
        int right = n - 1;
        for(int x : nums1) {
            if(x > nums2[index[left]]) {
                // 直接把x 放入到nums2 对应的下标 的ret中
                ret[index[left++]] = x;
            }else {
                // 把x 放入到nums2 的最大值对应的下标 的ret中
                ret[index[right--]] = x;
            }
        }

        return ret;
    }
}
